๋ฌธ์
๊ณ ์์ด๋ ๋๋ฌด ๊ท์ฝ๋ค. ์ฌ๋๋ค์ ๊ณ ์์ด๋ฅผ ๋๋ฌด ๊ท์ฌ์ํ๊ณ , ๊ฒฐ๊ตญ ๊ณ ์์ด์ ๋์ฑ ๊ฐ๊น์์ง๊ณ ์ถ์ด ๊ณ ์์ด์์ ์ํต์ ์ํ ๊ณ ์์ด ๋ง ๋ฒ์ญ๊ธฐ๋ฅผ ๋ฐ๋ช ํ๊ธฐ๋ก ํ๋ค. ์ด ๋ฒ์ญ๊ธฐ๋ ์ฌ๋์ ์ธ์ด๋ฅผ ๊ณ ์์ด์ ์ธ์ด๋ก, ๊ณ ์์ด์ ์ธ์ด๋ฅผ ์ฌ๋์ ์ธ์ด๋ก ๋ฐ๊พธ์ด ์ฃผ๋ ํฌ๋์ ๋ฐ๋ช ํ์ด ๋ ๊ฒ์ด๋ค.
ํ์ฌ ๊ณ ์์ด๋ง ๋ฒ์ญ๊ธฐ์ ๋ฒ ํ๋ฒ์ ์ด ๋์๋ค. ๊ทธ๋ฌ๋ ์ด ๋ฒ ํ๋ฒ์ ์ ์์ ์๋ง์ง์ฐฝ์ด๋ค. ๋ฒ ํ๋ฒ์ ์ ๋ฒ์ญ๊ธฐ๋ ๋ฌธ์์ด์ ์ฃผ๋ฉด ๊ทธ ์ค์์ ์ต๋ N๊ฐ์ ์ข ๋ฅ์ ์ํ๋ฒณ์ ๊ฐ์ง ์ฐ์๋ ๋ฌธ์์ด๋ฐ์ ์ธ์ํ์ง ๋ชปํ๋ค. ๊ต์ฅํ ๋ณ๋ก์ง๋ง ๊ทธ๋๋ง ์ด๊ฒ ์ต์ ์ด๋ผ๊ณ ์ฌ๋๋ค์ ์๊ฐํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฌธ์์ด์ด ์ฃผ์ด์ก์ ๋ ์ด ๋ฒ์ญ๊ธฐ๊ฐ ์ธ์ํ ์ ์๋ ์ต๋ ๋ฌธ์์ด์ ๊ธธ์ด๋ ์ผ๋ง์ธ์ง๊ฐ ๊ถ๊ธํด์ก๋ค.
๊ณ ์์ด์ ์ํตํ ์ ์๋๋ก ์ฐ๋ฆฌ๋ ํจ๊ป ๋ ธ๋ ฅํด๋ณด์.
์ , ์ถ๋ ฅ
์ ๋ ฅ
- ์ฒซ์งธ ์ค์๋ ์ธ์ํ ์ ์๋ ์ํ๋ฒณ์ ์ข ๋ฅ์ ์ต๋ ๊ฐ์ N์ด ์ ๋ ฅ๋๋ค. (1 < N โค 26)
- ๋์งธ ์ค์๋ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. (1 โค ๋ฌธ์์ด์ ๊ธธ์ด โค 100,000) ๋จ, ๋ฌธ์์ด์๋ ์ํ๋ฒณ ์๋ฌธ์๋ง์ด ํฌํจ๋๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ๋ฒ์ญ๊ธฐ๊ฐ ์ธ์ํ ์ ์๋ ๋ฌธ์์ด์ ์ต๋๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค.
๐ Logic
while(left <= right) {
// ๋ฒ์ ๋ฒ์ด๋๋ฉด ์ข
๋ฃ, ๊ธฐ๋ณธ์ ์ผ๋ก right๊ฐ ๋จผ์ ์์ง์
if (right >= str.length()) break;
char rightCh = str.charAt(right);
if ((left != right || right == 0) && prev == left)
wordIndexMap.put(rightCh, wordIndexMap.getOrDefault(rightCh, 0) + 1);
// ์์ง N๊ฐ ์ดํ์ธ ๊ฒฝ์ฐ, ๊ณ์ length๋ฅผ ๋๋ฆผ
if (wordIndexMap.size() <= N) {
maxLength = Math.max(maxLength, right - left + 1);
right++;
prev = left;
} else {
// N๊ฐ๊ฐ ์ฑ์์ ธ ๊ธฐ์กด์ ์ข
๋ฅ๋ฅผ ํ๋ ์ ์ธํ๋ ๊ฒฝ์ฐ
char leftCh = str.charAt(left);
int num = wordIndexMap.get(leftCh) - 1;
if(num == 0)
wordIndexMap.remove(leftCh);
else
wordIndexMap.put(leftCh, num);
left++;
}
}
Map์ผ๋ก ์ํ๋ฒณ ์ข ๋ฅ์ ๋น๋ ์๋ฅผ ์ ์ฅํ๋ค.-
Map์ดNsize๊ฐ ๋ ๊ฒฝ์ฐ์ ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ๋ก ๋๋ ,right๋ฅผ ๋๋ฆฌ๋ฉด์ ๊ธธ์ด๋ฅผ ์ฆ๊ฐ์ํค๊ฑฐ๋Map์์ ๊ธฐ์กด ์ํ๋ฒณ ํ๋๋ฅผ ์ง์ด๋ค.- ์ด๋,
left์ ์์นํ ๋ฌธ์์ด์ ๋ํดMap์์ ์กฐํํด๋ณด๊ณ ,left๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
- ์ด๋,
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
class Cat {
int maxLength = 0;
public Cat() {}
public void translate(int N, String str) {
Map<Character, Integer> wordIndexMap = new HashMap<>();
int left = 0;
int right = 0;
int prev = left;
while(left <= right) {
// ๋ฒ์ ๋ฒ์ด๋๋ฉด ์ข
๋ฃ, ๊ธฐ๋ณธ์ ์ผ๋ก right๊ฐ ๋จผ์ ์์ง์
if (right >= str.length()) break;
char rightCh = str.charAt(right);
if ((left != right || right == 0) && prev == left)
wordIndexMap.put(rightCh, wordIndexMap.getOrDefault(rightCh, 0) + 1);
// ์์ง N๊ฐ ์ดํ์ธ ๊ฒฝ์ฐ, ๊ณ์ length๋ฅผ ๋๋ฆผ
if (wordIndexMap.size() <= N) {
maxLength = Math.max(maxLength, right - left + 1);
right++;
prev = left;
} else {
// N๊ฐ๊ฐ ์ฑ์์ ธ ๊ธฐ์กด์ ์ข
๋ฅ๋ฅผ ํ๋ ์ ์ธํ๋ ๊ฒฝ์ฐ
char leftCh = str.charAt(left);
int num = wordIndexMap.get(leftCh) - 1;
if(num == 0)
wordIndexMap.remove(leftCh);
else
wordIndexMap.put(leftCh, num);
left++;
}
}
}
public int getMaxLength() {
return maxLength;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String str = br.readLine();
Cat cat = new Cat();
cat.translate(N, str);
System.out.println(cat.getMaxLength());
}
}
โ๏ธ Review
- ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฒ ๋์ด ์์ด๋์ด๋ ์ฝ๊ฒ ์ก์ ์ ์์์ผ๋ ๊ตฌํ์์ ์กฐ๊ธ ๋งํ๋ค.
right๋ฅผ ๋๋ฆฌ๋ฉด์prev๋ฅผ ํ์ธํด์ฃผ๋ ๊ณผ์ ์ด ํ์ํ๋ค.
๐ ์ถ์ฒ
- Baekjoon : https://www.acmicpc.net/problem/16472